Giải thuật tìm chu trình Euler Đường_đi_Euler

Bỏ cây cầu nối B với D, xây cây cầu nối A với C, đồ thị không có đỉnh bậc lẻ nên là đồ thị Euler

Giả sử G = (V, E) là đồ thị vô hướng, liên thông, tất cả các đỉnh đều có bậc chẵn hơn nữa G là hữu hạn. Khi đó, tất cả các đỉnh đều có bậc lớn hơn 1.

Giải thuật 2: Không đi qua cầu

Một cạnh của đồ thị G được gọi là cầu, nếu khi xóa cạnh đó khỏi đồ thị thì làm tăng số thành phần liên thông của G.

Giải thuật: Gọi chu trình cần tìm là C.

  1. Khởi tạo: Chọn một đỉnh bất kỳ cho vào C.
  2. Nếu G không còn cạnh nào thì dừng.
  3. Bổ sung: Chọn một cạnh nối đỉnh vừa chọn với một đỉnh kề với nó theo nguyên tắc: chỉ chọn cạnh cầu nếu không còn cạnh nào khác để chọn. Bổ sung cạnh vừa chọn và đỉnh cuối của nó vào C, xóa cạnh ấy khỏi G. Quay về bước 2.

Code mẫu

  1 #include <stdio.h>   2 #include <conio.h>  3 #define TRUE 1  4 #define FALSE 0  5 #define VAIN 99  6 #define MAX 10  7   8 int G[MAX][MAX];  9 // Ma Tran ke Dinh-Dinh (co Khuyen) 10 int S[MAX][MAX]; 11 // Ma Tran danh dau Cung da su dung 12 int Pred[MAX]; 13 // Mang Nua-Bac-Trong cua 1 Dinh 14 int Succ[MAX]; 15 // Mang Nua-Bac-Ngoai cua 1 Dinh 16 int path[MAX]; 17 // Mang duong di cua chu trinh 18  19 // khai bao ham 20 void ReadData(); 21 void PrintData(); 22 int Check(int k); 23 //bien toan cuc 24 int N, k, l = 0; 25 void Euler(); 26  27 void main() { 28     ReadData(); 29     PrintData(); 30     Euler(); 31 } 32  33 void ReadData() { 34     int i, j; 35     FILE * f = fopen("EU_in.txt", "rt"); 36  37     if (f == NULL) { 38         printf("\nError Loading File!\n"); 39         return; 40     } 41     fscanf(f, "%d", & N); // gia tri dau tien cho biet so dinh cua Do Thi G 42     for (i = 1; i <= N; i++) { 43         Succ[i] = Pred[i] = 0; 44         for (j = 1; j <= N; j++) { 45             S[i][j] = FALSE; 46             // danh dau Cung khong con su dung nua 47             fscanf(f, "%d", & G[i][j]); //lan luot doc cac phan tu MT ke 48         } 49     } 50     fclose(f); 51     for (i = 1; i <= N; i++) 52         for (j = 1; j <= N; j++) 53             if (G[i][j] > 0) { 54                 S[i][j] = TRUE; 55                 Succ[i]++; 56                 Pred[j]++; 57             } 58     // Tinh Bac moi Dinh  59 } 60  61 void PrintData() { 62     clrscr(); 63     int i, j; 64     printf("\nMa Tran Ke G[%d*%d]:\n", N, N); 65     for (i = 1; i <= N; i++) { 66         for (j = 1; j <= N; j++) 67             printf("%4d", G[i][j]); 68         printf("\n"); 69     } 70 } 71  72 void Euler() { 73     FILE * g = fopen("EU_out.txt", "wt"); 74     int i; 75     for (i = 1; i <= N; i++) 76         if ((Pred[i] + Succ[i]) % 2) // neu co dinh bac Le 77     { 78         printf("\nTon tai Dinh %d Bac Le!", i); 79         printf("\nKhong co chu trinh Euler\n"); 80         fclose(g); 81         return; 82     } 83     printf("\nDo thi co chu trinh Euler\n"); 84     int k, ok; 85     // kiem tra va in ra man hinh chu trinh Euler 1 net ve 86     printf("\nKet qua kiem tra xuat phat tu dinh 1:\n"); 87     for (k = 2; k <= N; k++) 88     // kiem tra xuat phat tu Dinh 1 89     { 90         if ((G[1][k] != 0)) 91         // co Cung noi Dinh 1 voi Dinh k 92         { 93             S[1][k] = FALSE; 94             // danh dau Cung(1,k) da duoc su dung 95             ok = Check(k); 96             // xet tiep Dinh k 97             if (ok == FALSE) 98                 S[1][k] = TRUE; //duong nay khong nen qua Dinh k=>tra danh dau 99             else // ok==TRUE100             {101                 //printf(" %d",k);//lan luot hien thi nguoc cac Dinh da qua102                 printf("Tong so dinh cua chu trinh: %d\n", l + 2);103                 fprintf(g, "%d\n", l + 2);104                 printf("Cac dinh cua duong di chu trinh:\n");105                 printf("1 %d ", k);106                 fprintf(g, "1 %d ", k);107                 for (int r = l - 1; r >= 0; r--) {108                     printf("%d ", path[r]);109                     fprintf(g, "%d ", path[r]);110                 }111                 fclose(g);112                 getch();113                 return;114             }115         }116     }117     // end for 118 }119 120 int Check(int k) // tiep tuc kiem tra, xuat phat tu Dinh k 121 {122     int i, j, ok;123     for (i = 1; i <= N; i++) {124         if ((S[k][i] == TRUE) && (G[k][i] != 0)) //co Cung tu k den cac Dinh con lai ?125         {126             S[k][i] = FALSE; // neu co, danh dau khong su dung lai Cung(k,i) nua127             ok = Check(i);128             // xet tiep Dinh i den cac Dinh khac129             if (ok == FALSE)130                 S[k][i] = TRUE; //lan nay khong nen qua Dinh i => bo danh dau131             else {132                 //printf(" %d",i);133                 path[l] = i;134                 l++;135                 return TRUE;136             }137         }138     }139     for (i = 1; i <= N; i++)140         // khi khong con Cung di tu Dinh k nua141         for (j = 1; j <= N; j++) // quet duyet do thi G xem da het Cung chua?142             if (S[i][j] == TRUE)143                 // neu con sot Cung tren Ma Tran danh dau S =>144                 return FALSE; //huong di theo Dinh k nay la sai=>chon Dinh k khac145     return TRUE;146     // thanh cong, tra ve cac dinh nguoc tren duong di Euler147 }